package inner_sort

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/25 23:59
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 无须递归的快速排序 - 使用栈实现
 * */
type QuickSortNonRecursive struct {
	FromHighToLow bool // true表示从高到低排序,默认 false 表示从低到高排序
}

func NewQuickSortNonRecursive(options ...C.Options) *BucketSort {
	opt := C.NewOptions(options...)
	return &BucketSort{
		FromHighToLow: opt.FromHighToLow,
	}
}

func (m *QuickSortNonRecursive) SortMethod(array []int) {
	if len(array) < 2 {
		return
	}
	stack := make([]int, 0, len(array))
	stack = append(stack, 0, len(array)-1)
	for len(stack) > 0 {
		l, r := stack[0], stack[1]
		stack = stack[2:]
		mid := m.quickSortSimples(array, l, r)
		if l < mid-1 {
			stack = append(stack, l, mid-1)
		}
		if mid+1 < r {
			stack = append(stack, mid+1, r)
		}
	}
	return
}

func (m *QuickSortNonRecursive) quickSortSimples(array []int, left, right int) int {
	mid, l := left, left+1
	for l <= right {
		if array[l] <= array[left] {
			mid++
			array[mid], array[l] = array[l], array[mid]
		}
		l++
	}
	if mid != left {
		array[mid], array[left] = array[left], array[mid]
	}
	return mid
}

func (m *QuickSortNonRecursive) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "QuickSortNonRecursive",
			NameCn: "内部排序:快速排序:非递归写法",
			ParamsDesc: map[string]string{
				"fromHighToLow": "true表示从高到低排序, 默认 false 表示从低到高排序",
			},
			Example: map[int]string{
				1: "输入[1,3,2],跳用SortMethod方法进行排序后，输出[1,2,3]",
			},
		},
	}
}
